//
// Created by Jisam on 2024/8/20 9:19.
// Solution of   #DX0008. 位运算
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
using namespace std;

#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr)
using namespace std;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};
const i64 INF = 0x3f3f3f3f,MOD = LONG_LONG_MAX;
template<typename T> T ksm(T b, T e, T m) {
    T r = 1;
    while (e) {
        if (e & 1) r = (r * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return r;
}
void solution()
{
    i64 n,k;
    cin >> n >> k;
    i64 cnt1=0;
    while(n){
        if(n%2) cnt1++;
        n/=2;
    }
    cout << ksm(2*1LL,k*2,MOD*1LL)*ksm(3*1LL,cnt1,MOD*1LL) << endl;
}


int main() {
    code_by_jisam;
    int T = 1;
    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}